//
// Created by Administrator on 2021/6/2.
//

/*
给你一个整数数组 nums 和一个整数k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

子数组大小 至少为 2 ，且
        子数组元素总和为 k 的倍数。
如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/continuous-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool checkSubarraySum(vector<int> &nums, int k) {
        // hash + 前缀和
        // 两个具有相同%前缀和的下标之间是一个和为k的整数倍的数组
        int n = (int) nums.size();
        if (n < 2) return false;
        unordered_map<int, int> mp;
        mp[0] = -1; // 放一个0在hash中
        int reminder = 0;
        for (int i = 0; i < n; ++i) {
            reminder = (reminder + nums[i]) % k;
            if (mp.find(reminder)!=mp.end()) {
                if (i - mp[reminder] >= 2) return true;
            } else
                mp[reminder] = i;
        }
        return false;
    }
};

int main() {
    vector<int> nums{23, 2, 4, 6, 7};
    Solution sol;
    cout << sol.checkSubarraySum(nums, 6) << endl;
    return 0;
}